import java.util.Stack;

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.key > key) {
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }

        if(parent.key > key) parent.left = node;
        if(parent.key < key) parent.right = node;
        return true;
    }


    //查找key是否存在
    public boolean search(int key) {
        if(root == null) return false;

        TreeNode cur = root;
        while(cur != null) {
            if(cur.key == key) {
                return true;
            }else if(cur.key > key) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return false;
    }


    //删除key的值
    public void remove(int key) {
        if(root == null) return;

        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.key == key) {
                removeNode(parent,cur);
                return;
            }else if(cur.key > key) {
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else if (parent.right == cur){
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if(cur == root) {
                root = root.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            // cur 左右子树都不为空， 找 cur左子树的最右一个结点 或者 cur右子树的最左一个结点来代替 cur
            TreeNode tmp = cur.right;
            TreeNode tmpPrev = cur;
            while(tmp.left != null) {
                tmpPrev = tmp;
                tmp = tmp.left;
            }
            cur.key = tmp.key;
            if(tmp == cur.right) {              //cur的右子树 没有左子树
                tmpPrev.right = tmp.right;
                return;
            }
            tmpPrev.left = tmp.right;

        }
    }


    //将搜索二叉树 转变成为 一个 按结点值的大小排序 的双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;

        TreeNode head = null;
        TreeNode prevTop = null;
        Stack<TreeNode> stack = new Stack<>();
        while(pRootOfTree != null || !stack.empty()) {
            if(pRootOfTree != null) {
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            } else {
                TreeNode top = stack.pop();
                //第一次弹出的结点为头结点
                if(head == null) {
                    head = top;
                }
                //
                if(prevTop != null) {
                    prevTop.right = top;
                }
                top.left = prevTop;
                prevTop = top;
                pRootOfTree = top.right;

            }
        }
        return head;
    }





    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }
}
